package com.tgy.leetcode;

import java.util.HashMap;
import java.util.Map;

class Trie {

    private static class Node{

        Map<Character,Node> map;
        boolean isWord;

        Node() {

            map = new HashMap<>();
            isWord = false;
        }
    }

    Map<Character,Node> map;
    int size;

    /** Initialize your data structure here. */
    public Trie() {

        map = new HashMap<>();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {

        if (word == null || word.length() == 0) {

            return;
        }

        char[] chars = word.toCharArray();
        Map<Character, Node> container = map;
        Node node = null;
        for (char aChar : chars) {

            node = container.get(aChar);
            if (node == null) {

                node = new Node();
                container.put(aChar,node);
            }
            container = node.map;
        }

        node.isWord = true;
        size++;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {

        if (word == null || word.length() == 0) {

            return false;
        }

        Node node = find(word);
        return node == null ? false:node.isWord;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {

        if (prefix == null || prefix.length() == 0) {

            return false;
        }

        Node node = find(prefix);
        return node != null;
    }

    private Node find(String word) {

        char[] chars = word.toCharArray();
        Map<Character, Node> container = map;
        Node node = null;
        for (char aChar : chars) {

            node = container.get(aChar);
            if (node == null) {

                return node;
            }
            container = node.map;
        }

        return node;
    }
}

public class _208_实现Trie {


    public static void main(String[] args) {

        Trie trie = new Trie();

        trie.insert("apple");
        System.out.println(trie.search("apple"));
        System.out.println(trie.search("app"));
        System.out.println(trie.startsWith("app"));
        trie.insert("app");
        System.out.println(trie.search("app"));
    }
}
